#leetcode题目10：正则表达式匹配
#难度：困难
#时间复杂度：O(m*n)
#空间复杂度：O(m*n)
#方法：动态规划
#目前暂时还没有吃透
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        cache=[[False]*(len(s)+1) for _ in range(len(p)+1)]
        cache[0][0]=True
        for i in range(1,len(p)):
            cache[i+1][0]=cache[i-1][0] and p[i]=='*'
        for i in range(len(p)):
            for j in range(len(s)):
                if p[i]=='*':
                    cache[i+1][j+1]=cache[i][j+1] or cache[i-1][j+1]
                    if p[i-1]==s[j] or p[i-1]=='.':
                        cache[i+1][j+1]|=cache[i+1][j]
                else:
                    cache[i+1][j+1]=cache[i][j] and (p[i]==s[j] or p[i]=='.')
        return cache[-1][-1]

#测试数据
s="aa"
p="a"
#预期输出：False
solution=Solution()
print(solution.isMatch(s,p))

s="aa"
p="a*"
#预期输出：True
solution=Solution()
print(solution.isMatch(s,p))

s="ab"
p=".*"
#预期输出：True
solution=Solution()
print(solution.isMatch(s,p))

s="aab"
p="c*a*b"
#预期输出：True
solution=Solution()
print(solution.isMatch(s,p))

s="mississippi"
p="mis*is*p*."
#预期输出：False
solution=Solution()
print(solution.isMatch(s,p))

